Cheatsheet [DS/A]

Binary search — the gap template

# Exact match — lo <= hi, both move past mid
lo, hi = 0, len(arr) - 1
while lo <= hi:
    mid = (lo + hi) // 2
    if arr[mid] == target: return mid
    elif arr[mid] < target: lo = mid + 1
    else: hi = mid - 1

# Boundary — find leftmost index where cond(i) is True
# lo < hi, hi = mid (NOT mid-1): mid might BE the answer
lo, hi = 0, len(arr) - 1
while lo < hi:
    mid = (lo + hi) // 2
    if cond(mid): hi = mid      # keep mid as candidate
    else: lo = mid + 1
# lo == hi == answer

# 153: cond = arr[mid] <= arr[-1]  (mid is in the right/rotated half)
# 33:  find pivot with 153, then exact-match in the correct half
# 981: import bisect; i = bisect.bisect_right(times, t) - 1

• Gotcha: hi = mid with lo <= hi loops forever. Boundary form pairs lo < hi with hi = mid; exact form pairs lo <= hi with mid ± 1. Never mix.
• Gotcha: rotated array — compare against arr[-1] (fixed anchor), not arr[lo] (moving target).
• Know bisect_left vs bisect_right: left = first ≥ x, right = first > x.

Overlapping intervals — the gap template

# 56. Merge Intervals — sort, then extend-or-append
intervals.sort(key=lambda x: x[0])
merged = [intervals[0]]
for start, end in intervals[1:]:
    if start <= merged[-1][1]:            # overlaps last merged
        merged[-1][1] = max(merged[-1][1], end)
    else:
        merged.append([start, end])

# Overlap test between two intervals (memorize this form):
# a and b overlap  ⟺  a.start <= b.end and b.start <= a.end

# 435. Non-overlapping Intervals — sort by END, greedy keep
intervals.sort(key=lambda x: x[1])
end = float("-inf"); keep = 0
for s, e in intervals:
    if s >= end:               # doesn't overlap the last kept
        keep += 1; end = e
return len(intervals) - keep      # removals; #452 arrows = keep itself

# 253. Meeting Rooms II — how many overlap at once (min rooms)
# min-heap of end times: push each end; if next start >= heap[0],
# pop first (reuse that room). Answer = max heap size seen.

• Which sort? "merge them / how many at peak" → sort by start. "max non-overlapping / fewest removals / fewest arrows" → sort by end. Wrong key is the classic interval miss.
• Gotcha: touching intervals — does [1,3] merge with [3,5]? Ask; it flips <= vs <. (In #435, s >= end treats touching as non-overlapping.)
• Gotcha: max() on the end — [1,10] then [2,3] must not shrink the merged end to 3.
• Plaid twist to expect: intervals arrive as transactions with timestamps + amounts; same merge, then aggregate per merged window.

Heap / Top-K — beyond Dijkstra

# 215. Kth largest — MIN-heap of size k (not max-heap of size n)
# Root is always the kth largest seen so far.
import heapq
heap = []
for num in nums:
    heapq.heappush(heap, num)
    if len(heap) > k:
        heapq.heappop(heap)        # evict smallest
return heap[0]                      # O(n log k), not O(n log n)

# One-liners worth knowing:
heapq.nlargest(k, nums)             # also takes key=...
heapq.heapify(arr)                  # O(n), in place

• Talking point: size-k min-heap gives O(n log k) — beats sorting when k ≪ n. Interviewers ask for this comparison on #215.
• #621 Task Scheduler: max-heap of counts + a cooldown queue of (ready_time, count). Greedy: always run the most frequent available task.

Design — LRU + TTL store

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity):
        self.cap = capacity
        self.cache = OrderedDict()

    def get(self, key):
        if key not in self.cache: return -1
        self.cache.move_to_end(key)      # mark most-recent
        return self.cache[key]

    def put(self, key, value):
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.cap:
            self.cache.popitem(last=False)  # evict oldest

# Plaid variant — KV store with TTL (the #981 shape):
# store[key] = list of (timestamp, value); reads bisect on timestamp.
# Lazy expiry: check ts on read instead of background cleanup — say why
# (no timers needed, O(1) writes; tradeoff = stale entries hold memory).

Backtracking — one template, all three problems

# 46. Permutations
def backtrack(path, remaining):
    if not remaining:
        result.append(path[:])          # COPY — path keeps mutating
        return
    for i in range(len(remaining)):
        path.append(remaining[i])                    # choose
        backtrack(path, remaining[:i] + remaining[i+1:])  # explore
        path.pop()                                   # unchoose

# 79. Word Search — grid DFS with undo:
# mark grid[r][c] = '#' before recursing, restore after. Same shape.

• Gotcha: appending path instead of path[:] — every result ends up empty (all point to the same mutated list).
• Gotcha: forgetting the restore in #79 — cells stay blocked for sibling paths, misses valid answers.

Trie — array children + pruning

# Prune a dead branch during backtracking — no parent pointer needed,
# the caller already has (parent) node + index in scope from the call site
child = node.children[char_index]
if child:
    ...
    backtrack(n_i, n_j, child)
    if child.word is None and all(c is None for c in child.children):
        node.children[char_index] = None   # nothing left through here, prune it

• all(c is None for c in child.children) is the array-trie version of "does this node have no children left" — a dict's emptiness check (not child.children) isn't available on a fixed array, so scan the 26 slots instead. Cheap, constant work either way.
• Prune at every level that recurses, including the outermost call (e.g. the root's direct children in the initial board scan) — pruning only inside the recursive helper leaves the top level uncleaned, so later starting cells keep re-entering already-exhausted branches.
• #212 Word Search II specifically: unpruned trie+DFS is often correct but too slow on adversarial boards (dense repeated letters, many overlapping words) — this isn't an optional polish step for that problem.

Monotonic stack — next greater / smaller

# 496/739. Next greater element to the right — decreasing stack of indices
res = [-1] * len(nums)
stack = []                          # holds indices, values decreasing
for i, x in enumerate(nums):
    while stack and nums[stack[-1]] < x:   # current x beats the top
        j = stack.pop()
        res[j] = x                  # x is j's next greater
    stack.append(i)
# 503 circular: iterate i in range(2n), use nums[i % n], only push i < n

• Decide direction by the goal: next greater → pop while top < x (stack stays decreasing). Next smaller → pop while top > x.
• Store indices, not values, when you need distance ("how many days"): i - j.
• Circular array (#503): walk range(2*len) with i % n; only push real indices.

Prefix sum — range totals in O(1)

# Range sum: prefix[i] = sum of first i elements; sum(l..r) = prefix[r+1]-prefix[l]
prefix = [0]
for x in nums: prefix.append(prefix[-1] + x)

# 560. Count subarrays summing to k — running sum + hashmap of seen sums
count = curr = 0
seen = {0: 1}                    # empty prefix seen once
for x in nums:
    curr += x
    count += seen.get(curr - k, 0)   # a prior prefix makes a window == k
    seen[curr] = seen.get(curr, 0) + 1

• Seed the map with {0: 1} — otherwise you miss subarrays that start at index 0.
• Count vs locate: hashmap of counts answers "how many"; hashmap of first index answers "longest such subarray" (#325).
• Divisible-by-k variant: key on curr % k instead of curr.

Running total vs stored history — the O(1) space check

# 724. Find Pivot Index — O(1) space, not O(n) prefix+suffix arrays
total = sum(nums)
left = 0
for i, x in enumerate(nums):
    right = total - left - x
    if left == right: return i
    left += x
return -1

• Same trick, multiplicative: #238 Product of Array Except Self — running product left→right into the output array, then fold in a running product right→left. No separate left/right arrays.
• Same trick, running extremum instead of running sum: #121 Best Time to Buy/Sell Stock (min-so-far) and #53 Maximum Subarray / Kadane's (max-ending-here).
• The test: do you need one number (a total, min, or max), or do you need to remember which past values occurred? One number → O(1) running variable. Which-value → hashmap or array.

2D Grids — setup, iteration, neighbors

# Instantiate — rows independent, no aliasing
rows, cols = 3, 4
grid = [[0] * cols for _ in range(rows)]
# bad_grid = [[0]*cols]*rows      # WRONG — all rows are one shared object

# Bounds-checked neighbor helper — reuse for BFS/DFS/backtracking
dirs_4 = [(-1,0), (1,0), (0,-1), (0,1)]

def get_neighbors(i, j, rows, cols):
    neighbors = []
    for dr, dc in dirs_4:
        ni, nj = i + dr, j + dc
        if 0 <= ni < rows and 0 <= nj < cols:
            neighbors.append((ni, nj))
    return neighbors

• 8-direction (with diagonals): add (-1,-1),(-1,1),(1,-1),(1,1) to dirs_4.
• Word Search-style problems: check the neighbor's value (e.g. board[ni][nj] == next_char) in the loop over get_neighbors's output — keep bounds-checking and value-checking as separate concerns, don't fold both into the helper.
• rows, cols = len(grid), len(grid[0]) — compute once, don't call len() inside a hot loop.

BFS vs DFS — templates + when to use

# BFS — shortest steps, unweighted. Queue + level snapshot.
from collections import deque
q = deque([start]); seen = {start}; steps = 0
while q:
    for _ in range(len(q)):        # one whole level per steps++
        node = q.popleft()
        if node == target: return steps
        for nb in graph[node]:
            if nb not in seen:
                seen.add(nb); q.append(nb)   # mark on enqueue
    steps += 1

# DFS — explore fully. Recursion (implicit stack) + visited.
seen = set()
def dfs(node):
    seen.add(node)
    for nb in graph[node]:
        if nb not in seen:
            dfs(nb)
# Grid: neighbors = 4 dirs; guard 0<=r<R, 0<=c<C before recursing.

• Shortest path is BFS only. DFS finds a path, not the shortest — the classic mix-up. Weighted edges → neither, use Dijkstra.
• Tree level-order (#102) is just the BFS template without a seen set (a tree can't revisit). The inner for loop is the level snapshot for #199 / zigzag.
• Deep DFS can blow the recursion stack (~1000 in Python). If depth could be large, convert to an explicit stack loop.